<?php 
/**
 * php常用算法
 * 
 */

//冒泡排序
function BubbleSort($arr){
	//获得数组总长度
	$num = count($arr);
	//正向遍历数组
	for($i = 1; $i < $num; $i++){
		//反向遍历数组
		for($j = $num - 1; $j >= $i; $j--){
			//相邻两个数比较
			if($arr[$j] < $arr[$j - 1]){
				//暂存较小的数
				$temp = $arr[$j - 1];
				//把较大的放前面
				$arr[$j-1] = $arr[$j];
				//较小的放后面
				$arr[$j] = $temp;
			}
		}
	}
	return $arr;
}

//交换法排序
function ExchangeSort($arr){
	$num = count($arr);
	//遍历数组
	for($i = 0; $i < $num - 1; $i++){
		//获得当前索引的下一个索引
		for($j = $i + 1; $j < $num; $j++){
			//比较相邻两个的值大小
			if($arr[$j] < $arr[$i]){
				//暂存较小的数
				$temp = $arr[$i];
				//把较大的放前面
				$arr[$i] = $arr[$j];
				//较小的放后面
				$arr[$j] = $temp;
			}
		}
	}
	return $arr;
}

//选择排序
function SelectSort($arr){
	$num = count($arr);
	//遍历数组
	for($i = 0; $i < $num - 1; $i++){
		//暂存当前值
		$temp = $arr[$i];
		//暂存当前索引簿
		$pos = $i;
		// 遍历当前索引以后的数据
		for($j = $i + 1; $j < $num; $j++){
			//如果小于当前值的
			if($arr[$j] < $temp){
				//暂存最小值
				$temp = $arr[$j];
				// 暂存位置
				$pos = $j;
			}
		}
		//把当前值放到算好的位置
		$arr[$pos] = $arr[$i];
		//把当前值换成算好的值
		$arr[$i] = $temp;
	}
	return $arr;
}

//插入排序
function InsertSort($arr){
	$num = count($arr);
	//遍历数组
	for($i = 1; $i < $num; $i++){
		//获得当前值
		$temp = $arr[$i];
		//获得当前值的前一个位置
		$pos = $i - 1;
		//如果当前值小于前一个值 且未到数组开头
		while($pos >= 0 && $temp < $arr[$pos]){
			//把前一个值往后放一位
			$arr[$pos + 1] = $arr[$pos];
			//位置递减
			$pos--;
		}
		$arr[$pos + 1] = $temp;
	}
	return $arr;
}

//快速排序
function QuickSort($arr){
	$num = count($arr);
	$l = $r = 0;
	$left = array();
	$right = array();
	//从索引的第二个开始遍历数组
	for($i = 1; $i < $num; $i++){
		//如果值小于索引1
		if($arr[$i] < $arr[0]){
			// 装入左索引数组(小于索引1的数据)
			$left[] = $arr[$i];
			$l++;
		}else{
			// 否则装入右索引中(大于索引1的数据)
			$right[] = $arr[$i];
			$r++;
		}
	}
	//如果左索引有值
	if($l > 1){
		$left = QuickSort($left);
	}
	//排序后的数组
	$new_arr = $left;
	//将当前数组第一个放到最后
	$new_arr[] = $arr[0];
	//如果右索引有值 则对右索引排序
	if($r > 1){
		$right = QuickSort($right);
	}
	//根据右索引的长度再次增加数据
	for($i = 0; $i < $r; $i++){
		$new_arr[] = $right[$i];
	}
	return $new_arr;

}



$arr1 = array(13,5,8,6,9,10,25);
$arr2 = array(2,8,4,3,9,52,6);
$arr3 = array(5,6,7,9,3,2,10);
$arr4 = array(9,5,7,3,1,12);
$arr5 = array(5,6,3,4,8,7,9);
header('Content-Type:text/html;charset=utf-8');
echo '<pre>';
echo '冒泡排序法<br/>';
print_r(BubbleSort($arr1));
echo '交换法排序<br/>';
echo '<br/>';
print_r(ExchangeSort($arr2));
echo '选择排序<br/>';
echo '<br/>';
print_r(SelectSort($arr3));
echo '插入排序<br/>';
echo '<br/>';
print_r(InsertSort($arr4));
echo '快速排序<br/>';
echo '<br/>';
print_r(QuickSort($arr5));
















?>